package course;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.stream.Collectors;

import linkedList.TreeNode;


public class BiTree {
    public static void main(String[] args) {

    }
}

class SolutionBiTree{
    /**144. 二叉树的前序遍历
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        s.push(root);
        while(!s.empty()){
            TreeNode node = s.pop();
            ans.add(Integer.valueOf(node.val));
            if(node.right != null) s.push(node.right);
            if(node.left != null) s.push(node.left);
        }
        return ans;
    }

    /**94. 二叉树的中序遍历
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode cur = root;
        while(!s.empty() || cur != null){
            if(cur != null){
                s.push(cur);
                cur = cur.left;
            }else{
                TreeNode node = s.pop();
                ans.add(node.val);
                cur = node.right;
            }
        }
        return ans;
    }

    /**145. 二叉树的后序遍历
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s.push(root);
        while(!s.empty()){
            TreeNode node = s.pop();
            s2.push(node);
            if(node.left != null) s.push(node.left);
            if(node.right != null) s.push(node.right);
        }
        List<Integer> ans = new ArrayList<>();
        while(!s2.empty())
            ans.add(s2.pop().val);
        return ans;
    }

    /**102. 二叉树的层序遍历
     * 
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return new ArrayList<List<Integer>>();
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> inner = new ArrayList<>();
        LinkedList<TreeNode> q = new LinkedList<>();
        q.add(root);
        TreeNode last = root;
        while(!q.isEmpty()){
            TreeNode node = q.remove();
            inner.add(node.val);
            if(node.left != null){
                q.add(node.left);
            }
            if(node.right != null){
                q.add(node.right);
            }
            if(node == last){
                ans.add(inner);
                inner = new ArrayList<>();
                last = q.isEmpty() ? null : q.getLast();            
            }
        }
        return ans;
    }

    /**107. 二叉树的层序遍历 II
     * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     */
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) return new ArrayList<List<Integer>>();
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> inner = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        Stack<List<Integer>> s = new Stack<>();
        q.add(root);
        TreeNode curLast = root, nxtLast = null;
        while(!q.isEmpty()){
            TreeNode node = q.remove();
            inner.add(node.val);
            if(node.left != null){
                q.add(node.left);
                nxtLast = node.left;
            }
            if(node.right != null){
                q.add(node.right);
                nxtLast = node.right;
            }
            // 结算当前层
            if(curLast == node){
                curLast = nxtLast;
                nxtLast = null;
                s.add(inner);
                inner = new ArrayList<>();
            }
        }
        while(!s.empty()){
            ans.add(s.pop());
        }
        return ans;
    }


    /**297. 二叉树的序列化与反序列化，这里采用按层序列化
     * 
     */
    public static String serialize(TreeNode root) {
        if(root == null) return null;
        List<String> ans = new ArrayList<>();
        LinkedList<TreeNode> q = new LinkedList<>();
        q.add(root); ans.add(String.valueOf(root.val));
        while(!q.isEmpty()){
            TreeNode node = q.remove();
            if(node.left != null){
                q.add(node.left);
                ans.add(String.valueOf(node.left.val));
            }else{
                ans.add("null");
            }
            if(node.right != null){
                q.add(node.right);
                ans.add(String.valueOf(node.right.val));
            }else{
                ans.add("null");
            }
        }
        return ans.stream().collect(Collectors.joining(","));
    }
    /**297. 二叉树的序列化与反序列化，这里采用层次
     * 
     */
    public static TreeNode deserialize(String data) {
        if(data == null) return null;
        List<String> strs = Arrays.stream( data.split(",")).collect(Collectors.toList());
        LinkedList<TreeNode> q = new LinkedList<>();
        int index = 0;
        TreeNode root = generateTreeNode(strs.get(index++));
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.pop();
            node.left = generateTreeNode(strs.get(index++));
            node.right = generateTreeNode(strs.get(index++));
            if(node.left != null) q.add(node.left);
            if(node.right != null) q.add(node.right);
        }

        return root;
    }
    
    private static TreeNode generateTreeNode(String val){
        if(val.equals("null") || val == null){
            return null;
        }else {
            return new TreeNode(Integer.parseInt(val));
        }
    }

    /**110. 判断平衡二叉树
     * 是指该树所有节点的左右子树的高度相差不超过 1。
     */
    public static boolean isBalanced(TreeNode root) {
        return isBalancedCore(root).isBalance;
    }
    private static class IsBalancedInfo{
        int high;
        boolean isBalance;
        IsBalancedInfo(int h, boolean i){ this.high = h; this.isBalance = i;}
    }
    private static IsBalancedInfo isBalancedCore(TreeNode root){
        if(root == null){
            return new IsBalancedInfo(0, true);
        }
        IsBalancedInfo leftInfo = isBalancedCore(root.left);
        IsBalancedInfo rightInfo = isBalancedCore(root.right);
        boolean isBalance = leftInfo.isBalance & rightInfo.isBalance;
        if(Math.abs(leftInfo.high - rightInfo.high) > 1) isBalance = false;
        return new IsBalancedInfo(Math.max(leftInfo.high, rightInfo.high) + 1, isBalance);
    }

    /**543. 二叉树的直径(最大路径距离)
     * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
     * 两节点之间路径的 长度 由它们之间边数表示。
     */
    public int diameterOfBinaryTree(TreeNode root) {
        return diameterOfBinaryTreeCore(root).maxLength;
    }

    private static class BinaryTreeInfo{
        int high; // 当前节点的高度
        int maxLength; // 当前节点作为子树的最大路径距离
        BinaryTreeInfo(int h, int m){ this.high = h; this.maxLength = m;}
    }
    private static BinaryTreeInfo diameterOfBinaryTreeCore(TreeNode root){
        if(root == null)
            return new BinaryTreeInfo(0, 0);
        BinaryTreeInfo leftInfo = diameterOfBinaryTreeCore(root.left);
        BinaryTreeInfo rightInfo = diameterOfBinaryTreeCore(root.right);

        // 当前树的高度
        int high = Math.max(leftInfo.high, rightInfo.high) + 1;
        // 当前树作为子树的最大路径距离
        // 左树最大路径距离，佑树，和经过当前节点的最大路径距离
        int maxLength = Math.max(leftInfo.maxLength, rightInfo.maxLength);
        maxLength = Math.max(maxLength, leftInfo.high + rightInfo.high);

        return new BinaryTreeInfo(high, maxLength);
    }

    /** 333.最大二叉搜索子树
     * 二叉搜索树：左树的所有节点一定小于根节点，右树一定大于，返回最大搜索子树的头结点和最大节点数
     */
    public static int[] largestSubBST(TreeNode root){
        LargestSubBSTInfo resInfo = largestSubBSTCore(root);
        int[] ans = new int[2];
        ans[0] = resInfo.head == null ? -1 : resInfo.head.val;
        ans[1] = resInfo.maxSize;
        return ans;
    }
    private static class LargestSubBSTInfo{
        int max; 
        int min;
        boolean isBST; // 是否是搜索二叉树
        int maxSize; // 搜索二叉树的最大节点数
        TreeNode head; // 最大搜索二叉子树的头结点
        LargestSubBSTInfo(int max, int min, boolean isBST, int maxSize, TreeNode head){
            this.max = max;
            this.min = min;
            this.isBST = isBST;
            this.maxSize = maxSize;
            this.head = head;
        }
    }

    private static LargestSubBSTInfo largestSubBSTCore(TreeNode root){
        if(root == null) {
            return new LargestSubBSTInfo(
                Integer.MIN_VALUE,
                Integer.MAX_VALUE,
                true,
                0,
                null
            );
        }
        LargestSubBSTInfo leftInfo = largestSubBSTCore(root.left);
        LargestSubBSTInfo rightInfo = largestSubBSTCore(root.right);

        int max = Math.max(root.val, Math.max(leftInfo.max, rightInfo.max));
        int min = Math.min(root.val, Math.min(leftInfo.min, rightInfo.min));
        boolean isBST = false;
        int maxSize = 0;
        TreeNode head = null;

        if(root.val > leftInfo.max &&
            root.val < rightInfo.min &&
            leftInfo.isBST && rightInfo.isBST){
                // 是搜索二叉树
                isBST = true;
                maxSize = leftInfo.maxSize + rightInfo.maxSize + 1;
                head = root;
        }
        else{
            if(leftInfo.maxSize >= rightInfo.maxSize){
                maxSize = leftInfo.maxSize;
                head = leftInfo.head;
            }else{
                maxSize = rightInfo.maxSize;
                head = rightInfo.head;
            }
        }
        return new LargestSubBSTInfo(max, min, isBST, maxSize, head);
    }

    /** 派对的最大快乐值
     * 
     * 链接：https://www.nowcoder.com/questionTerminal/a5f542742fe24181b28f7d5b82e2e49a
        来源：牛客网

        整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。
        这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则：
        1.如果某个员工来了，那么这个员工的所有直接下级都不能来。
        2.派对的整体快乐值是所有到场员工快乐值的累加。
        3.你的目标是让派对的整体快乐值尽量大。
        给定一棵多叉树，请输出派对的最大快乐值。
     */
    public static int PartyMaxHappy(MultiTree root){
        PartyHappyInfo info = PartyMaxHappyCore(root);
        int ans = Math.max(info.absent, info.present);
        return ans;
    }
    private static class MultiTree{
        int val;
        List<MultiTree> children;
        MultiTree(int val){
            this.val = val;
            this.children = new ArrayList<>();
        }
    }
    private static class PartyHappyInfo{
        int present; // 到场的快乐值
        int absent; // 缺席的快乐值
        PartyHappyInfo(int present, int absent){ this.present = present; this.absent = absent;}
    }
    private static PartyHappyInfo PartyMaxHappyCore(MultiTree root){
        if(root == null){
            return new PartyHappyInfo(0, 0);
        }
        int present = root.val, absent = 0;
        if(root.children.size() > 0){
            for(MultiTree child : root.children){
                PartyHappyInfo childInfo = PartyMaxHappyCore(child);
                present += childInfo.absent;
                absent += Math.max(childInfo.absent, childInfo.present);
            }
        }
        return new PartyHappyInfo(present, absent);
    }





}
